package pro.softzhang.algo.lc500;

import com.alibaba.fastjson.JSON;
import pro.softzhang.algo.common.TreeNode;
import pro.softzhang.algo.flag.difficulty.DRed;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 广度优先顺序遍历二叉树
 */
@DRed
public class LC515_FindLargestValueInEachTreeRow {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1, new TreeNode(2, null, null), new TreeNode(3, null, null));
        List<Integer> largestValues = new LC515_Solution().largestValues(root);
        System.out.println(JSON.toJSONString(largestValues));
    }
}

class LC515_Solution {
    public List<Integer> largestValues(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        int current = 0, next = 0;
        if(root != null) {
            q.offer(root);
            current = 1;
        }

        List<Integer> values = new ArrayList<>();
        int max = Integer.MIN_VALUE;
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            current--;
            max = Math.max(max, node.val);
            if(node.left != null) {
                q.offer(node.left);
                next++;
            }
            if(node.right != null) {
                q.offer(node.right);
                next++;
            }
            if(current == 0) {
                values.add(max);
                max = Integer.MIN_VALUE;
                current = next;
                next = 0;
            }
        }

        return values;
    }
}